# Fibonacci
# Recurrsion (递归)
# 我调用我自己
# Two key points:
# - Termination condition (终止条件)
# F0 = 0
# F1 = 1
# 
# - Formula (公式)
# Fn = F(n - 1) + F(n - 2) (n >= 2)

# Write a function that return nth fibonacci number.
# [0, 1, 1, 2, 3, 5, 8]
# Parameter:
# - n: the index of the number in fibonacci
# Return:
# - The nth fibonacci number
def get_nth_fibonacci(n):
  if n == 1:
    return 0
  elif n == 2:
    return 1
  else:
    return get_nth_fibonacci(n - 1) + get_nth_fibonacci(n - 2)

print(get_nth_fibonacci(4))

# get_nth_fibonacci(4)
# get_nth_fibonacci(3) + get_nth_fibonacci(2)
# get_nth_fibonacci(2) + get_nth_fibonacci(1) + get_nth_fibonacci(2)
# 1 + 0 + 1
# 2
